#include <bits/stdc++.h>

#define eb emplace_back
#define ep emplace
#define fi first
#define se second
#define in read<int>()
#define lin read<ll>()
#define rep(i, x, y) for(int i = (x); i <= (y); i++)
#define per(i, x, y) for(int i = (x); i >= (y); i--)
#define epr(i, x, y) for(int i = h[x], y = e[i].v; i; i = e[i].nxt, y = e[i].v)

using namespace std;

using ll = long long;
using db = double;
using pii = pair < int, int >;
using vec = vector < int >;
using veg = vector < pair < int, ll > >;

template < typename T > T read() {
	T x = 0; bool f = 0; char ch = getchar();
	while(!isdigit(ch)) f |= ch == '-', ch = getchar();
	while(isdigit(ch)) x = x * 10 + (ch ^ 48), ch = getchar();
	return f ? -x : x;
}

template < typename T > void chkmax(T &x, const T &y) { x = x > y ? x : y; }
template < typename T > void chkmin(T &x, const T &y) { x = x < y ? x : y; }

const int N = 5e5 + 10;
const ll INF = 0x3f3f3f3f3f3f3f3f;

int n, m, h[N], ndn, cnt;
ll dis[N], tot[N];
bool vis[N];
unordered_map < int, int > f[N];

struct edge { int v, c, w, nxt; } e[N];
void link(int x, int y, int c, int w) { e[++cnt] = (edge) { y, c, w, h[x] }; h[x] = cnt; }

veg G[N];

priority_queue < pair < ll, int >, vector < pair < ll, int > >, greater < pair < ll, int > > > q;

void dijk() {
	memset(dis, 0x3f, sizeof dis); dis[1] = 0; q.ep(dis[1], 1);
	while(q.size()) {
		int x = q.top().se; q.pop(); if(vis[x]) continue; vis[x] = true;
		if(x == n) return printf("%lld\n", dis[x]), void();
		for(auto v : G[x]) {
			int y; ll w; tie(y, w) = v;
			if(dis[y] > dis[x] + w) dis[y] = dis[x] + w, q.ep(dis[y], y);
		}
	} puts("-1");
}

int main() {
#ifndef ONLINE_JUDGE
	freopen("1.in", "r", stdin);
#endif
	ndn = n = in, m = in;
	rep(i, 1, m) {
		int u = in, v = in, c = in, w = in;
		link(u, v, c, w); link(v, u, c, w);
	}
	rep(x, 1, n) {
		epr(i, x, y) tot[e[i].c]++, (f[x][e[i].c] == 0) && (f[x][e[i].c] = ++ndn);
		epr(i, x, y) (tot[e[i].c] == 1) && (G[x].eb(y, 0), 1);
		epr(i, x, y) tot[e[i].c] = 0;
	}
	rep(x, 1, n) {
		epr(i, x, y) tot[e[i].c] += e[i].w;
		epr(i, x, y) {
			G[x].eb(y, e[i].w);
			G[x].eb(y, tot[e[i].c] - e[i].w);
			G[f[x][e[i].c]].eb(y, tot[e[i].c] - e[i].w);
			G[x].eb(f[y][e[i].c], 0);
		}
		epr(i, x, y) tot[e[i].c] = 0;
	} dijk();
	return 0;
}
